#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <chrono>
using namespace std;
using namespace chrono;
class Solution
{
public:
    vector<vector<int>> ans;
    vector<int> slice;
    map<vector<int>, int> hashmap;
    void dfs(int cur, int target, int csum, vector<int> &nums)
    {
        if (slice.size() > 4)
            return;
        if (csum == target && slice.size() == 4)
        {
            vector<int> tmp = slice;
            sort(tmp.begin(), tmp.end());
            if (hashmap[tmp] == 0)
            {
                ans.push_back(tmp);
                hashmap[tmp]++;
            }
            return;
        }
        for (int i = cur; i < nums.size(); ++i)
        {
            slice.push_back(nums[i]);
            dfs(i + 1, target, csum + nums[i], nums);
            slice.pop_back();
        }
    }
    vector<vector<int>> fourSum(vector<int> &nums, int target)
    {
        dfs(0, target, 0, nums);
        return ans;
    }
};
int main()
{
    vector<int> nums = {-497, -494, -484, -477, -453, -453, -444, -442, -428, -420, -401, -393, -392, -381, -357, -357, -327, -323, -306, -285, -284, -263, -262, -254, -243, -234, -208, -170, -166, -162, -158, -136, -133, -130, -119, -114, -101, -100, -86, -66, -65, -6, 1, 3, 4, 11, 69, 77, 78, 107, 108, 108, 121, 123, 136, 137, 151, 153, 155, 166, 170, 175, 179, 211, 230, 251, 255, 266, 288, 306, 308, 310, 314, 321, 322, 331, 333, 334, 347, 349, 356, 357, 360, 361, 361, 367, 375, 378, 387, 387, 408, 414, 421, 435, 439, 440, 441, 470, 492};
    int target = 1682;
    Solution slover;
    auto start = system_clock::now();
    slover.fourSum(nums, target);
    auto end = system_clock::now();
    auto duration = duration_cast<microseconds>(end - start);
    cout << "花费了"
         << double(duration.count()) * microseconds::period::num / microseconds::period::den
         << "秒" << endl;
    return 0;
}